package demo1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode createTree() {
        TreeNode n1 = new TreeNode(3);
        TreeNode n2 = new TreeNode(9);
        TreeNode n3 = new TreeNode(20);
        TreeNode n4 = new TreeNode(15);
        TreeNode n5 = new TreeNode(7);
        n1.left = n2;
        n1.right = n3;
        n3.left = n4;
        n3.right = n5;
        return n1;
    }
    //前序遍历二叉树
    public void preorder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preorder(root.left);
        preorder(root.right);
    }
    //对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean n = isSymmetrics(root.left,root.right);
        return n;
    }
    public boolean isSymmetrics(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        boolean le = isSymmetrics(left.left,right.right);
        if (!le) {
            return false;
        }
        boolean ri = isSymmetrics(left.right,right.left);
        return ri;
    }
    //二叉树的层序遍历
    public void levelOrder1(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur == null) {
                continue;
            }
            System.out.print(cur.val + " ");
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();

            while (size-- != 0) {
                TreeNode cur = queue.poll();
                if (cur == null) {
                    continue;
                }
                list.add(cur.val);
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
            if (!list.isEmpty()) {
                lists.add(list);
            }
        }
        return lists;
    }

    //二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root  == q) {
            return root;
        }
        TreeNode leftT = lowestCommonAncestor(root.left,p,q);
        TreeNode righT = lowestCommonAncestor(root.right,p,q);
        if (leftT != null && righT != null) {
            return root;
        } else if (leftT != null) {
            return leftT;
        } else {
            return righT;
        }
    }
    //根据前序和中序 来构建二叉树
    public int i;
    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        TreeNode root = buildTreechild(preorder,inorder,0,inorder.length - 1);
        return root;
    }
    public TreeNode buildTreechild1(int[] preorder, int[] inorder, int inbegin, int inend) {
        if (inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[i]);
        int rootIndex = findindex(preorder,inorder);
        if (rootIndex == -1) {
            return null;
        }
        i++;

        root.left = buildTreechild(preorder,inorder,inbegin,rootIndex - 1);
        root.right = buildTreechild(preorder,inorder,rootIndex + 1,inend);
        return root;
    }
    private int findindex(int[] preorder, int[] inorder) {
        int val = preorder[i];
        for (int j = 0; j < inorder.length; j++) {
            if (inorder[j] == val) {
                return j;
            }
        }
        return -1;
    }
    //根据中序和后序构造二叉树
    public int j;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        j = postorder.length - 1;
        TreeNode root = buildTreechild(inorder,postorder,0,inorder.length - 1);
        return root;
    }
    private TreeNode buildTreechild(int[] inorder, int[] postorder, int inbegin, int inend) {
        if (inbegin > inend) {
            return null;
        }

        TreeNode root = new TreeNode(postorder[j]);
        int rootIndex = findIndexofI(inorder,inbegin,inend,postorder[j]);
        if (rootIndex == -1) {
            return null;
        }
        j--;

        root.right = buildTreechild(inorder,postorder,rootIndex + 1,inend);
        root.left = buildTreechild(inorder,postorder,inbegin,rootIndex - 1);

        return root;

    }
    private int findIndexofI(int[] inorder, int inbegin, int inend, int key) {
        for (int k = inbegin; k <= inend; k++) {
            if (inorder[k] == key) {
                return k;
            }
        }
        return -1;
    }
}
